iT邦幫忙

2024 iThome 鐵人賽

0
自我挑戰組

C++自學系列 第 26

Day 26 STL容器(set, map, unordered_set, unordered_map)

  • 分享至 

  • xImage
  •  

STL容器(set, map, unordered_set, unordered_map)
**set:**是一種存儲唯一元素的容器,其中每個元素自動排序。set不允許重複的元素,並且在內部使用平衡二叉樹來維護有序性
‧唯一性:set中的所有元素都唯一,重複元素不會被插入
‧自動排序:元素按照從小到大自動排序
‧高效查找:基於平衡樹結構,查找、插入和刪除的時間複雜度為O(log n)
‧不支持隨機存取:不能像vector一樣通過索引訪問元素

**map:**是一種存儲鍵值對的容器,其中每個鍵必須唯一,並且鍵值對按照鍵的順序自動排序,map內部使用平衡二叉樹來進行元素的管理
‧鍵唯一:每個鍵在map中都是唯一的,重複鍵將覆蓋舊的值
‧自動排序:鍵按照從小到大的順序自動排序
‧高校查找:基於平衡樹,查找、插入和刪除的時間複雜度為O(log n)
‧鍵值對存儲:每個元素是一個鍵值對

**unordered_set:**是一種存儲唯一元素的 STL 容器,但與set不同的是,unordered_set使用哈希表來存儲元素,因此元素的存儲順序是無序的。這使得它在查找、插入和刪除操作上比set更快,時間複雜度平均為 O(1),而不是 O(log n)
‧唯一性:unordered_set中每個元素都是唯一的,插入重複的元素會被忽略
‧無序性:元素是根據哈希值存儲的,因此不保證元素的順序
‧哈希表:使用哈希表進行內部管理,因此查找、插入和刪除操作的時間複雜度平均為 O(1),最壞情況為 O(n)
‧效率:對於大量數據且不需要保持順序的狀況下,unordered_set通常比set更高效

**unordered_map:**unordered_map和map類似,都是存儲鍵值對的容器,但 unordered_map使用哈希表實現,因此鍵值對是無序的。它提供了比map更快的查找速度,因為哈希表的查找、插入和刪除的時間複雜度通常為 O(1)
‧鍵唯一:每個鍵都是唯一的,重複鍵將覆蓋舊值
‧無序存儲:元素照哈希表進行存儲,沒有固定的順序
‧快速查找:基於哈希表,查找、插入和刪除的平均時間複雜度為 O(1),最壞情況下為 O(n)
‧需要哈希函數:unordered_map需要對鍵進行哈希,因此鍵必須是可哈希的類型(如整數、字串)


上一篇
Day 25 STL容器(vector, deque, list)
下一篇
Day 27 STL佚代器與演算法(尋訪與操作容器)
系列文
C++自學30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言